1. Field of the Invention
The present invention relates generally to automatic integrated circuit placement and routing tools, and more particularly to routing algorithms for standard-cell and gate-array design.
2. Description of the Prior Art
Takashi Fujii, et al., describe in "A Multi-Layer Channel Router with New Style of Over-the-Cell Routing," Proceedings of the 29th ACM/IEEE Design Automation Conference, 1992, pp. 585-588, a style of over-the-cell routing, where a cell structure is introduced. Recent advances in manufacturing technology make it possible to use three or four layers of interconnections in the fabrication of semiconductor devices (chips). In a "standard cell" approach, extending channels to handle multi-layered regions is necessary. Several prior art multi-layer channel routers have been developed that rely on high-speed processing for channel routing. In order to reduce channel heights, over-the-cell channel routers have been developed in which their routing models include terminals that have been limited to being placed on outlines of the cells. Thus, the routing region is divided into two regions, e.g., channels and regions over the cells. Since such routers should be applied to each of regions individually, the results depend on the selection of nets to be routed over the cells. This selection is a key challenge.
Takashi Fujii, et al., propose an over-the-cell routing where a cell structure is introduced that makes maximum use of the available cell regions. Terminals exist not only on the top and bottom edges of cells but also around the horizontal center line. Takashi Fujii, et al., regard the region between the central terminals of the upper and lower cell rows as an expanded channel. The router handles that region as a group, where connections to central terminals are achieved while avoiding same metal layer obstacles in the cells. Since it is not necessary to preliminarily select a set of nets which will run over the cells, their router globally performs the routing with a minimal channel height. It is a goal of the routing to shorten the length of polysilicon wires, suitable for high-performance chips. Experimental results are said to show that their router achieves a second objective of size reduction. The length of polysilicon wires is reported to be substantially shortened, as compared with those not considering the polysilicon terminals.
It is typically assumed that four layers are available for routing, e.g., a polysilicon layer and three metal layers: metal-1, metal-2 and metal-3. The polysilicon layer, metal-1, metal-2 and metal-3, are all used for vertical and horizontal wiring. For each layer, there is an imaginary grid system superimposed over the region to be routed. Wires preferably are routed to run along the grid lines in a rectilinear fashion, in order to reduce the number of variables that would be generated by runs that could be at an infinite number of places. An electrical connection between two wires on adjacent layers is implemented with a "via". Such vias are typically placed on the intersections of grid lines for the layers to be connected, again to reduce the number of variables, which speeds a solution.
Takashi Fujii, et al., introduce a cell structure in which obstacles may exist in opposite ends of a cell. An exemplary cell (in the cited article) has the shape of a rectilinear polygon. Terminals are located on a perimeter of the cell and around a horizontal center line. Equi-potential terminals are allowed to be only on a common vertical column. Terminals around a center line are referred to as "central terminals". Polysilicon layer-terminals exist only on the perimeter of the cell. All of the central terminals are of metal-2. A metal-3 wire is allowed to run along any of the metal-3 grid lines, since metal-3 is typically not used in a cell layout. Metal-2 wire is routed while avoiding metal-2 obstacles.
Takashi Fujii, et al., consider an "expanded channel" routing region, which is defined to be a maximal rectilinear polygon surrounding the central terminals and horizontal center lines in upper and lower cell rows. A lower half of the upper cell row is referred to as a first over-the-cell region. And an upper half of the lower cell row is referred to as a second over-the-cell region. In such over-the-cell regions, only metal-2 and metal-3 wires can be used. The grid lines of metal-1 and metal-3 are restricted to a single direction and are referred to as "tracks". The grid lines of polysilicon layer and metal-2 are restricted to an orthogonal direction and are referred to as "columns". The partial grid lines of metal-2, included in the cell regions, are referred to as the "cell columns". The partial grid lines of metal-3, included in the cell regions, are referred to as the cell tracks.
The routing problem for an expanded channel is different from a conventional channel. There may exist obstacles in the routing region. The shape of the expanded channel is not rectangular, since the central lines are not aligned horizontally. Metal-1 and metal-3 can be used for horizontal wires in the conventional channel, however only metal-1 can be used in the over-the-cell region. Polysilicon terminals are located inside the expanded channel. The grid interval of metal-1 in the over-the-cell region need not be equal to one in the conventional channel.
In one example of the prior art, routing for an expanded channel includes the steps of doing a specification of a channel, routing from central terminals, changing polysilicon terminals to metal-2, and track assignment. In the first step, the expanded channel is defined, based on the cell data. The second step performs the connections to central terminals, avoiding obstacles in the cells. In the third step, the polysilicon wires connecting to polysilicon terminals are routed to metal-2 wires, for as many polysilicon layer-terminals as is possible. This layer changing is achieved by using a pattern which is a best-fit of several patterns. The changing is required to make maximum use of metal-3 tracks, since a metal-2 wire can connect to a metal-3 wire only with a via. As a result of such changing, the length of wires is shortened. According to inherent vertical constraints, horizontal wires of subnets are assigned to tracks of metal-1 and metal-3 in the fourth step.
In order to make maximum use of the over-the-cell regions, Takashi Fujii, et al., introduced a cell structure in which terminals are located around a horizontal center line. The proposed router processes an expanded channel between central terminals in an upper cell row and ones in a lower cell row. Their experimental results indicated to them that such a router is effective in reducing a die size and can shorten the length of polysilicon wires.
In the prior art, cell pins have to be on metal-2, and have to be placed manually by a user. Such metal-2 pin positions are not instance based. Therefore, unused metal-2 pins can result and become a blockage to other signal connections. By avoiding such blockages, the connection lengths and the chip area can be reduced. Unused metal-2 pins also have the undesirable affect of introducing excess capacitance to a chip design.